package com.tucc.hello.leetcode.no1_400.no1_200.no21_40.no37;

import cn.hutool.json.JSONUtil;

import java.util.*;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution_BAD {

    public static void main(String[] args) {
        Solution_BAD solution = new Solution_BAD();
        char[][] board = solution.readData(TEST_DATA);
        solution.solveSudoku(board);
        solution.printBoard(board);
    }

    public void solveSudoku(char[][] board) {
        Set<Character> template = new HashSet<>();
        for (int i = 1; i <= 9; i++) {
            template.add((char) ('0' + i));
        }
        Set<Task> taskSet = new HashSet<>();
        Map<Integer, Set<Task>> taskMap1 = new HashMap<>();
        Map<Integer, Set<Task>> taskMap2 = new HashMap<>();
        Map<Integer, Set<Task>> taskMap3 = new HashMap<>();
        initTask(board, taskSet, taskMap1, taskMap2, taskMap3, template);

        printTask(taskSet);
        System.out.println("current task num :" + taskSet.size());
        int lastTaskNum = taskSet.size();
        while(!taskSet.isEmpty()) {
            trySolve(board, taskSet, taskMap1, taskMap2, taskMap3);
            System.out.println("===========");
            printTask(taskSet);
            System.out.println("current task num :" + taskSet.size());
            if(taskSet.size() == lastTaskNum){
                break;
            }
            lastTaskNum = taskSet.size();
        }

    }

    private void trySolveRecursion(char[][] board, Set<Task> taskSet,
                                   Map<Integer, Set<Task>> taskMap1,
                                   Map<Integer, Set<Task>> taskMap2,
                                   Map<Integer, Set<Task>> taskMap3){
        while(!taskSet.isEmpty()) {
            Iterator<Task> iterator = taskSet.iterator();
            while(iterator.hasNext()){
                Task task = iterator.next();
                if(task.isSure()){
                    Character ch = task.getSure();
                    int i = task.i, j = task.j;
                    removeImpossibleValue(taskMap1,  i, ch);
                    removeImpossibleValue(taskMap2,  j, ch);
                    removeImpossibleValue(taskMap3,  i / 3 * 3 + j / 3, ch);
                    board[i][j] = ch;
                    iterator.remove();
                }
                if(taskSet.isEmpty()){
                    return;
                }
            }
        }
    }

    private void trySolve(char[][] board, Set<Task> taskSet,
                          Map<Integer, Set<Task>> taskMap1,
                          Map<Integer, Set<Task>> taskMap2,
                          Map<Integer, Set<Task>> taskMap3){

        Iterator<Task> iterator = taskSet.iterator();
        while(iterator.hasNext()){
            Task task = iterator.next();
            if(task.isSure()){
                Character ch = task.getSure();
                int i = task.i, j = task.j;
                removeImpossibleValue(taskMap1,  i, ch);
                removeImpossibleValue(taskMap2,  j, ch);
                removeImpossibleValue(taskMap3,  i / 3 * 3 + j / 3, ch);
                board[i][j] = ch;
                iterator.remove();
            }
        }
    }

    private void printTask(Set<Task> taskSet){
        if(taskSet != null){
            for(Task task : taskSet){
                System.out.println(String.format("%d %d, maybe %s", task.i, task.j, task.possible));
            }
        }
    }

    private void initTask(char[][] board, Set<Task> taskSet,
                          Map<Integer, Set<Task>> taskMap1,
                          Map<Integer, Set<Task>> taskMap2,
                          Map<Integer, Set<Task>> taskMap3,
                          Set<Character> template) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] == '.') {
                    Task task = new Task(template, i, j);
                    taskSet.add(task);
                    addTask(taskMap1, task, i);
                    addTask(taskMap2, task, j);
                    addTask(taskMap3, task, i / 3 * 3 + j / 3);
                }
            }
        }
        removeImpossible(board, taskMap1, taskMap2, taskMap3);
    }

    private void removeImpossible(char[][] board,
                                   Map<Integer, Set<Task>> taskMap1,
                                   Map<Integer, Set<Task>> taskMap2,
                                   Map<Integer, Set<Task>> taskMap3){
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                char ch = board[i][j];
                if (ch != '.') {
                    removeImpossibleValue(taskMap1,  i, ch);
                    removeImpossibleValue(taskMap2,  j, ch);
                    removeImpossibleValue(taskMap3,  i / 3 * 3 + j / 3, ch);
                }
            }
        }
    }
    private void removeImpossibleValue(Map<Integer, Set<Task>> taskMap,int index, Character ch){
        Set<Task> tasks = taskMap.get(index);
        if(tasks != null){
            for(Task task : tasks){
                task.removeImpossible(ch);
            }
        }
    }

    private void addTask(Map<Integer, Set<Task>> taskMap, Task task, int index) {
        Set<Task> tasks = taskMap.get(index);
        if (tasks == null) {
            tasks = new HashSet<>();
            taskMap.put(index, tasks);
        }
        tasks.add(task);
    }

    class Task {
        Set<Character> possible;
        int i;
        int j;

        public Task(Set<Character> set, int i, int j) {
            this.possible = new HashSet<>(set);
            this.i = i;
            this.j = j;
        }

        public boolean isSure() {
            return possible.size() == 1;
        }

        public Character getSure() {
            return possible.iterator().next();
        }

        public boolean removeImpossible(Character ch){
            return possible.remove(ch);
        }
    }

    public char[][] readData(String data) {
        List<String> stringList = JSONUtil.toList(data, String.class);
        char[][] chars = new char[stringList.size()][];
        for (int i = 0; i < chars.length; i++) {
            String string = stringList.get(i);
            string = string.substring(1, string.length() - 1).replaceAll("[\",]", "");
            chars[i] = string.toCharArray();
        }
        return chars;
    }

    private void printBoard(char[][] board){
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                char ch = board[i][j];
                System.out.print(ch);
            }
            System.out.println();
        }
    }
    public static final String TEST_DATA2 =
            "[[\"5\",\"3\",\".\",\".\",\"7\",\".\",\".\",\".\",\".\"]," +
                    "[\"6\",\".\",\".\",\"1\",\"9\",\"5\",\".\",\".\",\".\"]," +
                    "[\".\",\"9\",\"8\",\".\",\".\",\".\",\".\",\"6\",\".\"]," +
                    "[\"8\",\".\",\".\",\".\",\"6\",\".\",\".\",\".\",\"3\"]," +
                    "[\"4\",\".\",\".\",\"8\",\".\",\"3\",\".\",\".\",\"1\"]," +
                    "[\"7\",\".\",\".\",\".\",\"2\",\".\",\".\",\".\",\"6\"]," +
                    "[\".\",\"6\",\".\",\".\",\".\",\".\",\"2\",\"8\",\".\"]," +
                    "[\".\",\".\",\".\",\"4\",\"1\",\"9\",\".\",\".\",\"5\"]," +
                    "[\".\",\".\",\".\",\".\",\"8\",\".\",\".\",\"7\",\"9\"]]";


    public static final String TEST_DATA = "[[\".\",\".\",\"9\",\"7\",\"4\",\"8\",\".\",\".\",\".\"],[\"7\",\".\",\".\",\".\",\".\",\".\",\".\",\".\",\".\"],[\".\",\"2\",\".\",\"1\",\".\",\"9\",\".\",\".\",\".\"],[\".\",\".\",\"7\",\".\",\".\",\".\",\"2\",\"4\",\".\"],[\".\",\"6\",\"4\",\".\",\"1\",\".\",\"5\",\"9\",\".\"],[\".\",\"9\",\"8\",\".\",\".\",\".\",\"3\",\".\",\".\"],[\".\",\".\",\".\",\"8\",\".\",\"3\",\".\",\"2\",\".\"],[\".\",\".\",\".\",\".\",\".\",\".\",\".\",\".\",\"6\"],[\".\",\".\",\".\",\"2\",\"7\",\"5\",\"9\",\".\",\".\"]]";
}
